package 面试常见刷题;

import java.util.Arrays;

public class 二分查找 {
    /*
    核心注意点：1.如果是找一个值的位置，while中是<= ,右边界是length-1;
              2.如果是找左边第一个或者右边第一个，while中是<，有边界是length，left的值变成mid+1，right的值变成mid
     */
    public static void main(String[] args) {
        int[] data = {1, 3, 4, 4, 4, 5, 7, 11};
        System.out.println(binarySearch(data,5));
        System.out.println(binarySearchLeft(data, 12));
        System.out.println(binarySearchRight(data, 12));
    }

    private static int binarySearch(int[] data, int target) {
        int left = 0, right = data.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (data[mid] == target) {
                return mid;
            }
            if (data[mid] > target) {
                right = mid - 1;
            }
            if (data[mid] < target) {
                left = mid + 1;
            }
        }
        return -1;
    }

    private static int binarySearchLeft(int[] data, int target) {
        int left = 0, right = data.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (data[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private static int binarySearchRight(int[] data, int target) {
        int left = 0, right = data.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (data[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left - 1;
    }
}
